{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Check If a String Contains All Binary Codes of Size K"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #hash-table #string #hash-function #rolling-hash"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #哈希表 #字符串 #哈希函数 #滚动哈希"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: hasAllCodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #检查一个字符串是否包含所有长度为 K 的二进制子串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个二进制字符串&nbsp;<code>s</code>&nbsp;和一个整数&nbsp;<code>k</code>&nbsp;。如果所有长度为 <code>k</code>&nbsp;的二进制字符串都是 <code>s</code>&nbsp;的子串，请返回 <code>true</code> ，否则请返回 <code>false</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"00110110\", k = 2\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>长度为 2 的二进制串包括 \"00\"，\"01\"，\"10\" 和 \"11\"。它们分别是 s 中下标为 0，1，3，2 开始的长度为 2 的子串。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"0110\", k = 1\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>长度为 1 的二进制串包括 \"0\" 和 \"1\"，显然它们都是 s 的子串。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"0110\", k = 2\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>长度为 2 的二进制串 \"00\" 没有出现在 s 中。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 5 * 10<sup>5</sup></code></li>\n",
    "\t<li><code>s[i]</code> 不是<code>'0'</code> 就是 <code>'1'</code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= 20</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [check-if-a-string-contains-all-binary-codes-of-size-k](https://leetcode.cn/problems/check-if-a-string-contains-all-binary-codes-of-size-k/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [check-if-a-string-contains-all-binary-codes-of-size-k](https://leetcode.cn/problems/check-if-a-string-contains-all-binary-codes-of-size-k/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"00110110\"\\n2', '\"0110\"\\n1', '\"0110\"\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        l = len(s)\n",
    "        if (l + 1 - k) < (2 ** k):\n",
    "            return False\n",
    "        bitmap = [False] * (2 ** k)\n",
    "        for i in range(l + 1 - k):\n",
    "            v = int(s[i: i+k], 2)\n",
    "            bitmap[v] = True\n",
    "        return all(bitmap)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        l = len(s)\n",
    "        if (l + 1 - k) < (2 ** k):\n",
    "            return False\n",
    "        bitmap = [False] * (2 ** k)\n",
    "        for i in range(l + 1 - k):\n",
    "            v = int(s[i: i+k], 2)\n",
    "            bitmap[v] = True\n",
    "\n",
    "        return all(bitmap)\n",
    "        # if (len(s) + 1 - k) < 2 ** k: return False\n",
    "        # def hasAllCodesHelper(b: str, k: int) -> bool:\n",
    "        #     if k == 0:\n",
    "        #         if s.find(b) == -1:\n",
    "        #             return False\n",
    "        #         else:\n",
    "        #             return True\n",
    "        #     if not hasAllCodesHelper(b + '0', k - 1): return False\n",
    "        #     if not hasAllCodesHelper(b + '1', k - 1): return False\n",
    "        #     return True\n",
    "        # return hasAllCodesHelper(\"\", k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        res = [False] * pow(2, k)\n",
    "        i=0\n",
    "        j=i+k\n",
    "        while j <= len(s):\n",
    "            num = int(s[i:j], 2)\n",
    "            res[num] = True\n",
    "            i += 1\n",
    "            j += 1\n",
    "\n",
    "        is_All = True\n",
    "        for i in range(len(res)):\n",
    "            if not res[i]:\n",
    "                is_All = False\n",
    "                break\n",
    "\n",
    "        return is_All"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        N, n = 1 << 21, len(s)\n",
    "        st = [False] * N\n",
    "\n",
    "        for i in range(n - k + 1):\n",
    "            temp = int(s[i:i+k], 2)\n",
    "            st[temp] = True\n",
    "        \n",
    "        for i in range(1 << k):\n",
    "            if not st[i]:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        if len(s) < (1 << k) + k - 1:\n",
    "            return False\n",
    "        \n",
    "        num = int(s[:k], base=2)\n",
    "        exists = set([num])\n",
    "\n",
    "        for i in range(1, len(s) - k + 1):\n",
    "            num = (num - ((ord(s[i - 1]) - 48) << (k - 1))) * 2 + (ord(s[i + k - 1]) - 48)\n",
    "            exists.add(num)\n",
    "        \n",
    "        return len(exists) == (1 << k)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        if len(s) < (1 << k) - 1:\n",
    "            return False\n",
    "        num = int(s[:k], base=2)\n",
    "        exists = set([num])\n",
    "        for i in range(1, len(s) - k + 1):\n",
    "            num = (num - ((ord(s[i - 1]) - 48) << (k - 1))) * 2 + (ord(s[i + k - 1]) - 48)\n",
    "            exists.add(num)\n",
    "        return len(exists) == (1 << k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        if len(s) < (1 << k) + k - 1:\n",
    "            return False\n",
    "        \n",
    "        num = int(s[:k], base=2)\n",
    "        exists = {num}\n",
    "        dd = {'0':0, '1':1}\n",
    "\n",
    "        for i in range(1, len(s) - k + 1):\n",
    "            x = dd[s[i - 1]]\n",
    "            num = (num - (x << (k - 1))) * 2 + dd[s[i + k - 1]]\n",
    "            exists.add(num)\n",
    "        \n",
    "        return len(exists) == (1 << k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        n = len(s)\n",
    "        if n < 2 ** k:\n",
    "            return False\n",
    "        tot = set()\n",
    "        for i in range(n - k + 1):\n",
    "            tmp = int(s[i: i + k], 2)\n",
    "            tot.add(tmp)\n",
    "            if len(tot) == 2 ** k:\n",
    "                return True \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        if len(s) < k:\n",
    "            return False\n",
    "\n",
    "        if len(s) - (k - 1) < (1 << k):\n",
    "            return False\n",
    "            \n",
    "        left = 0\n",
    "        right = k - 1\n",
    "\n",
    "        val = 0\n",
    "\n",
    "        for i in range(k):\n",
    "            val *= 2\n",
    "            val += int(s[i])\n",
    "\n",
    "        seen = set()\n",
    "        seen.add(val)\n",
    "\n",
    "        po = 1 << (k - 1)\n",
    "        left += 1\n",
    "        right += 1\n",
    "        while right < len(s):\n",
    "            val -= int(s[left - 1]) * po\n",
    "            val <<= 1\n",
    "            val += int(s[right])\n",
    "\n",
    "            seen.add(val)\n",
    "\n",
    "            left += 1\n",
    "            right += 1\n",
    "\n",
    "        \n",
    "        return len(seen) == (1 << k)\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        if len(s) < (1 << k) + k - 1:\n",
    "            return False\n",
    "        \n",
    "        num = int(s[:k], base=2)\n",
    "        exists = set([num])\n",
    "\n",
    "        for i in range(1, len(s) - k + 1):\n",
    "            num = (num - ((ord(s[i - 1]) - 48) << (k - 1))) * 2 + (ord(s[i + k - 1]) - 48)\n",
    "            exists.add(num)\n",
    "        \n",
    "        return len(exists) == (1 << k)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\r\n",
    "        if k >= len(s) or (1 << k) > len(s) - k + 1:\r\n",
    "            return False\r\n",
    "        st = set()\r\n",
    "        t = 0\r\n",
    "        mask = (1 << k) - 1\r\n",
    "        for i in range(k):\r\n",
    "            t = t * 2 + int(s[i])\r\n",
    "        st.add(t)\r\n",
    "        for i in range(k, len(s)):\r\n",
    "            t = t * 2 + int(s[i])\r\n",
    "            t &= mask\r\n",
    "            st.add(t)\r\n",
    "        # 长度为 1 的二进制非零数 : 1\r\n",
    "        # 长度为 2 的二进制非零数 : 2\r\n",
    "        # 长度为 n 的二进制非零数 : 2 ^ (n - 1)\r\n",
    "        # 和 = 2^n - 1\r\n",
    "        return len(st) == mask + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        n = len(s)\n",
    "        vis = set()\n",
    "        for i in range(n - k + 1):\n",
    "            vis.add(int(s[i: i + k], 2))\n",
    "            if len(vis) == 2 ** k:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        n = len(s)\n",
    "        if k > n:\n",
    "            return False\n",
    "        seen = set()\n",
    "        res = 0\n",
    "        for i in range(k):\n",
    "            res <<= 1\n",
    "            res += int(s[i])\n",
    "        seen.add(res)\n",
    "        for i in range(k, n):\n",
    "            res <<= 1\n",
    "            if int(s[i - k]):\n",
    "                res &= ~(1 << k)\n",
    "            \n",
    "            res += int(s[i])\n",
    "            seen.add(res)\n",
    "        \n",
    "        return len(seen) == pow(2, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        k_set = set()\n",
    "        ls = len(s)\n",
    "        if ls < k:\n",
    "            return False\n",
    "        for i in range(ls - k + 1):\n",
    "            si_bin = s[i:i+k]\n",
    "            si_dec = int(si_bin, 2)\n",
    "            if si_dec not in k_set:\n",
    "                k_set.add(si_dec)\n",
    "        if len(k_set) != 2**k:\n",
    "            return False\n",
    "        else:\n",
    "            return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        if len(s) < k:\n",
    "            return False\n",
    "        left = 0\n",
    "        right = k - 1\n",
    "\n",
    "        val = 0\n",
    "\n",
    "        for i in range(k):\n",
    "            val *= 2\n",
    "            val += int(s[i])\n",
    "\n",
    "        seen = set()\n",
    "        seen.add(val)\n",
    "\n",
    "        po = 1 << (k - 1)\n",
    "        left += 1\n",
    "        right += 1\n",
    "        while right < len(s):\n",
    "            val -= int(s[left - 1]) * po\n",
    "            val <<= 1\n",
    "            val += int(s[right])\n",
    "\n",
    "            seen.add(val)\n",
    "\n",
    "            left += 1\n",
    "            right += 1\n",
    "\n",
    "        \n",
    "        for i in range(1 << k):\n",
    "            if i not in seen:\n",
    "                return False\n",
    "        \n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        n = len(s)\n",
    "        if k > n:\n",
    "            return False\n",
    "        seen = set()\n",
    "        res = 0\n",
    "        for i in range(k):\n",
    "            res <<= 1\n",
    "            res += int(s[i])\n",
    "        seen.add(res)\n",
    "        for i in range(k, n):\n",
    "            res <<= 1\n",
    "            res &= ~(1 << k)\n",
    "            res += int(s[i])\n",
    "            seen.add(res)\n",
    "        \n",
    "        return len(seen) == pow(2, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        if len(s) < k:\n",
    "            return False\n",
    "        left = 0\n",
    "        right = k - 1\n",
    "\n",
    "        val = 0\n",
    "\n",
    "        for i in range(k):\n",
    "            val *= 2\n",
    "            val += int(s[i])\n",
    "\n",
    "        seen = set()\n",
    "        seen.add(val)\n",
    "\n",
    "        po = 1 << (k - 1)\n",
    "        left += 1\n",
    "        right += 1\n",
    "        while right < len(s):\n",
    "            val -= int(s[left - 1]) * po\n",
    "            val <<= 1\n",
    "            val += int(s[right])\n",
    "\n",
    "            seen.add(val)\n",
    "\n",
    "            left += 1\n",
    "            right += 1\n",
    "\n",
    "        \n",
    "        return len(seen) == (1 << k)\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        k_set = set()\n",
    "        ls = len(s)\n",
    "        if ls < k:\n",
    "            return False\n",
    "        for i in range(ls - k + 1):\n",
    "            si_bin = s[i:i+k]\n",
    "            si_dec = int(si_bin, 2)\n",
    "            if si_dec not in k_set:\n",
    "                k_set.add(si_dec)\n",
    "        return len(k_set) == 2**k\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\r\n",
    "        if k >= len(s):\r\n",
    "            return False\r\n",
    "        st = set()\r\n",
    "        t = 0\r\n",
    "        mask = (1 << k) - 1\r\n",
    "        for i in range(k):\r\n",
    "            t = t * 2 + int(s[i])\r\n",
    "        st.add(t)\r\n",
    "        for i in range(k, len(s)):\r\n",
    "            t = t * 2 + int(s[i])\r\n",
    "            t &= mask\r\n",
    "            st.add(t)\r\n",
    "        # 长度为 1 的二进制非零数 : 1\r\n",
    "        # 长度为 2 的二进制非零数 : 2\r\n",
    "        # 长度为 n 的二进制非零数 : 2 ^ (n - 1)\r\n",
    "        # 和 = 2^n - 1\r\n",
    "        return len(st) == mask + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        # for i in range(2 ** k):\n",
    "        #     s_ = bin(i)[2:]\n",
    "        #     ch = s_.zfill(k)\n",
    "        #     if ch not in s:\n",
    "        #         return False\n",
    "        # else:\n",
    "        #     return True\n",
    "        if len(s) < (1 << k) + k - 1:\n",
    "            return False\n",
    "        \n",
    "        exists = set(s[i:i+k] for i in range(len(s) - k + 1))\n",
    "        return len(exists) == (1 << k)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        s_len = len(s)\n",
    "        if s_len - k + 1 < 2**k:\n",
    "            return False\n",
    "        curr = set()\n",
    "        for i in range(s_len+1-k):\n",
    "            curr.add(s[i:k+i])\n",
    "        if len(curr) >= 2 ** k:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        if len(s)<(1<<k)+k-1:\n",
    "            return False\n",
    "        exist=set(s[i:i+k] for i in range(len(s)-k+1))\n",
    "        return len(exist)==(1<<k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        # for i in range(2 ** k):\n",
    "        #     s_ = bin(i)[2:]\n",
    "        #     ch = s_.zfill(k)\n",
    "        #     if ch not in s:\n",
    "        #         return False\n",
    "        # else:\n",
    "        #     return True\n",
    "        if len(s) < (1 << k) + k - 1:\n",
    "            return False\n",
    "        \n",
    "        key=set()\n",
    "        for i in range(len(s)-k+1):\n",
    "            key.add(s[i:i+k:])\n",
    "        return len(key)==1<<k\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        if len(s) < (1 << k) + k - 1:\n",
    "            return False\n",
    "        \n",
    "        exists = set(s[i:i+k] for i in range(len(s) - k + 1))\n",
    "        return len(exists) == (1 << k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        target = 1 << k\n",
    "        if len(s) < target + k - 1:\n",
    "            return False\n",
    "        seen = set()\n",
    "        for i in range(len(s)-k+1):\n",
    "            seen.add(s[i:i+k])\n",
    "            if len(seen) == target:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        s_len = len(s)\n",
    "        if s_len < 2 ** k:\n",
    "            return False\n",
    "        curr = set()\n",
    "        for i in range(s_len+1-k):\n",
    "            curr.add(s[i:k+i])\n",
    "        if len(curr) >= 2 ** k:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        if len(s) < (1 << k) + k - 1:\n",
    "            return False\n",
    "        \n",
    "        exists = set(s[i:i+k] for i in range(len(s) - k + 1))\n",
    "        return len(exists) == (1 << k)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        target = 1 << k\n",
    "        if len(s) < target + k - 1:\n",
    "            return False\n",
    "        seen = set()\n",
    "        for i in range(len(s)-k+1):\n",
    "            seen.add(s[i:i+k])\n",
    "            if len(seen) == target:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        if len(s) < (1 << k) - 1:\n",
    "            return False\n",
    "        exist = set(s[i:i+k] for i in range(len(s) - k + 1))\n",
    "        return len(exist) == (1 << k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        n = len(s)\n",
    "        if n < 2 ** k + k - 1:\n",
    "            return False\n",
    "        return len(set(s[i:i+k] for i in range(n - k + 1))) == 2 ** k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        if len(s) < (1<<k)+k -1:\n",
    "            return False\n",
    "        exist = set(s[i:i+k] for i in range (len(s)-k+1))\n",
    "        return len(exist) == (1<<k)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        n = len(s)\n",
    "\n",
    "        if k >= n or n - k + 1 < (1 << k):\n",
    "            return False\n",
    "\n",
    "        hashset = set()\n",
    "\n",
    "        for i in range(0, n - k + 1):\n",
    "            hashset.add(s[i: i + k])\n",
    "\n",
    "        return len(hashset) == (1 << k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        s_len = len(s)\n",
    "        if s_len < 2 ** k:\n",
    "            return False\n",
    "        curr = set()\n",
    "        for i in range(s_len+1-k):\n",
    "            curr.add(s[i:k+i])    \n",
    "            #所有长度为k的子数组都放进curr,set里面的元素不重复\n",
    "        if len(curr) >= 2 ** k:\n",
    "            return True   \n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        k_set = set()\n",
    "        ls = len(s)\n",
    "        if ls < k:\n",
    "            return False\n",
    "        for i in range(ls - k + 1):\n",
    "            si_bin = s[i:i+k]\n",
    "            k_set.add(si_bin)\n",
    "        return len(k_set) == 2**k\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        count = Counter()\n",
    "        for i in range(len(s) - k + 1):\n",
    "            count[s[i:i + k]] += 1\n",
    "        for i in range(2 ** k):\n",
    "            b = bin(i)[2:]\n",
    "            if len(b) < k:\n",
    "                b = \"0\" * (k - len(b)) + b\n",
    "            if b not in count:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        dc = {}\n",
    "        for i in range(len(s) - k + 1):\n",
    "            dc[s[i:i+k]] = 1\n",
    "        return len(dc) == 2 ** k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        return len(set(s[i:i + k] for i in range(len(s) - k + 1))) == 2 ** k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        dic = set()\n",
    "        for  i in range(len(s) - k + 1):\n",
    "            dic.add(s[i:i+k])\n",
    "        if len(dic) == 2**k:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        length = len(s)\n",
    "        table ={}\n",
    "        for i in range(length-k+1):\n",
    "            table[s[i:i+k]] = 1\n",
    "        return True if len(table)==2**k else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        n=len(s)\n",
    "        num=2**k\n",
    "        sign=set()\n",
    "        for i in range(n-k+1):\n",
    "            sign.add(s[i:i+k])\n",
    "        if len(sign)==num:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        seen = set()\n",
    "        target = 1 << k\n",
    "        for i in range(len(s)-k+1):\n",
    "            seen.add(s[i:i+k])\n",
    "            if len(seen) == target:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        return len(set(s[i:i+k] for i in range(len(s) - k + 1))) == 2 ** k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        n=len(s)\n",
    "        sign=set()\n",
    "        for i in range(n-k+1):\n",
    "            sign.add(s[i:i+k])\n",
    "        return len(sign)==2**k\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\r\n",
    "        st = set()\r\n",
    "        for i in range(len(s)-k+1):\r\n",
    "            st.add(s[i:i+k])\r\n",
    "        return len(st) == 2**k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        n = len(s)\n",
    "        vis = set()\n",
    "        for i in range(k, n + 1):\n",
    "            t = s[i - k: i]\n",
    "            vis.add(t)\n",
    "            if len(vis) == 2 ** k: return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        left, right = 0, k\n",
    "        num_set = set()\n",
    "        while right <= len(s):\n",
    "            num_set.add(s[left: right])\n",
    "            left += 1\n",
    "            right += 1\n",
    "        # print(num_set)\n",
    "        return len(num_set) == 2**k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        ss=set()\n",
    "        for i in range(len(s)-k+1):\n",
    "            ss.add(s[i:i+k])\n",
    "        return len(ss)==(1<<k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        ss=set()\n",
    "        for i in range(len(s)-k+1):\n",
    "            ss.add(s[i:i+k])\n",
    "        return len(ss)==(2**k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        # if len(s) < (1 << k) + k - 1:\n",
    "        #     return False\n",
    "        \n",
    "        exists = set(s[i:i+k] for i in range(len(s) - k + 1))\n",
    "        return len(exists) == (1 << k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        ans = set()\n",
    "        n = len(s)\n",
    "        for i in range(n-k+1):\n",
    "            ans.add(s[i:i+k])\n",
    "        return len(ans) == 2**k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        ss = set(s[i:i+k] for i in range(1+len(s)-k))\n",
    "        return len(ss) == 1 << k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        m = set()\n",
    "        for i in range(len(s) - k + 1):\n",
    "            m.add(s[i: i + k])\n",
    "        return len(m) == 2 ** k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        st = set()\n",
    "        for i in range(len(s) - k + 1):\n",
    "            st.add(s[i:i + k])\n",
    "        if '0' * k not in st:   return False\n",
    "        for i in range(2 ** (k - 1), 2 ** k):\n",
    "            if str(bin(i)[2:]) not in st:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        \"\"\"\n",
    "        对于子串上的每一位字符,都有 0 和 1 两种可能\n",
    "        所以, k长度的子串的排列可能性 x = 2**k\n",
    "        用窗口遍历字符串, 把每个窗口中的子串加入哈希表, 最后统计哈希表的长度是否 = x\n",
    "        \"\"\"\n",
    "        n = len(s)\n",
    "        if k >= n:\n",
    "            return False\n",
    "\n",
    "        m = set()\n",
    "        x = 2**k\n",
    "        for i in range(n-k+1):\n",
    "            win = s[i:i+k]\n",
    "            m.add(win)\n",
    "        return len(m) == x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        n = len(s)\n",
    "        vis = set()\n",
    "        for i in range(k, n + 1):\n",
    "            t = s[i - k: i]\n",
    "            vis.add(t)\n",
    "        return len(vis) == 2 ** k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        d=set()\n",
    "        for i in range(0,len(s)-k+1):\n",
    "            d.add(s[i:i+k])\n",
    "            # print(s[i:i+k])\n",
    "        return len(d)==1<<k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        \"\"\"\n",
    "        对于子串上的每一位字符,都有 0 和 1 两种可能\n",
    "        所以, k长度的子串的排列可能性 x = 2**k\n",
    "        用窗口遍历字符串, 把每个窗口中的子串加入哈希表, 最后统计哈希表的长度是否 = x\n",
    "        \"\"\"\n",
    "        n = len(s)\n",
    "        if k >= n:\n",
    "            return False\n",
    "\n",
    "        m = set()\n",
    "        x = 2**k\n",
    "        for i in range(n-k+1):\n",
    "            win = s[i:i+k]\n",
    "            m.add(win)\n",
    "        return len(m) == x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        d=set()\n",
    "        for i in range(0,len(s)-k+1):\n",
    "            d.add(s[i:i+k])\n",
    "            # print(s[i:i+k])\n",
    "        return len(d)==1<<k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        se = set()\n",
    "        for i in range(len(s) - k + 1):\n",
    "            se.add(s[i: i+k])\n",
    "        if(len(se) == 2**k):\n",
    "            return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        if(len(s) < k):\n",
    "            return False\n",
    "        tSet = set()\n",
    "        cnt = 0\n",
    "        for i in range(len(s)-k+1):\n",
    "            if(s[i:i+k] not in tSet):\n",
    "                cnt += 1\n",
    "                tSet.add(s[i:i+k])\n",
    "            if(cnt == 2**k):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        if(len(s) < k):\n",
    "            return False\n",
    "        tSet = set()\n",
    "        cnt = 0\n",
    "        for i in range(len(s)-k+1):\n",
    "            if(s[i:i+k] not in tSet):\n",
    "                cnt += 1\n",
    "                tSet.add(s[i:i+k])\n",
    "            if(cnt == 2**k):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        d=set()\n",
    "        for i in range(0,len(s)-k+1):\n",
    "            d.add(s[i:i+k])\n",
    "            # print(s[i:i+k])\n",
    "        return len(d)==1<<k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        dic = set()\n",
    "        for  i in range(len(s) - k + 1):\n",
    "            dic.add(s[i:i+k])\n",
    "        for num in range(2**k):\n",
    "            binary_str = format(num, '0' + str(k) + 'b')\n",
    "            if not binary_str in dic:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        if(len(s) < k):\n",
    "            return False\n",
    "        tSet = set()\n",
    "        cnt = 0\n",
    "        for i in range(len(s)-k+1):\n",
    "            if(s[i:i+k] not in tSet):\n",
    "                cnt += 1\n",
    "                tSet.add(s[i:i+k])\n",
    "            if(cnt == 2**k):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        key=set()\n",
    "        for i in range(len(s)-k+1):\n",
    "            key.add(s[i:i+k:])\n",
    "        return len(key)==1<<k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\r\n",
    "        st = set()\r\n",
    "        for i in range(len(s)-k+1):\r\n",
    "            st.add(s[i:i+k])\r\n",
    "        return len(st) == 1 << k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasAllCodes(self, s: str, k: int) -> bool:\n",
    "        num = len(s)\n",
    "        if num <= k:\n",
    "            return False\n",
    "\n",
    "        num_list = []\n",
    "        for i in range(num-k+1):\n",
    "            num1 = s[i:i+k]\n",
    "            num_list.append(num1)\n",
    "        num_list = list(set(num_list))\n",
    "        a = len(num_list)\n",
    "        if a == 2 ** k:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
